package org.aplombh.java.awcing.basic.graph.graphTraversal.bfs;

import org.aplombh.java.utils.Queue;
import org.aplombh.java.utils.SwapUtils;

import java.util.HashMap;
import java.util.Scanner;

/**
 * 在一个 3×3 的网格中，1∼8 这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3 的网格中。
 * <p>
 * 例如：
 * <p>
 * 1 2 3
 * x 4 6
 * 7 5 8
 * 在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。
 * <p>
 * 我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
 * <p>
 * 1 2 3
 * 4 5 6
 * 7 8 x
 * 例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。
 * <p>
 * 交换过程如下：
 * <p>
 * 1 2 3   1 2 3   1 2 3   1 2 3
 * x 4 6   4 x 6   4 5 6   4 5 6
 * 7 5 8   7 5 8   7 x 8   7 8 x
 * 现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。
 * <p>
 * 输入格式
 * 输入占一行，将 3×3 的初始网格描绘出来。
 * <p>
 * 例如，如果初始网格如下所示：
 * <p>
 * 1 2 3
 * x 4 6
 * 7 5 8
 * 则输入为：1 2 3 x 4 6 7 5 8
 * <p>
 * 输出格式
 * 输出占一行，包含一个整数，表示最少交换次数。
 * <p>
 * 如果不存在解决方案，则输出 −1。
 * <p>
 * 输入样例：
 * 2  3  4  1  5  x  7  6  8
 * 输出样例
 * 19
 */
public class EightDigital_845 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);


        StringBuilder start = new StringBuilder();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                start.append(scanner.next());
            }
        }

        EightDigital eightDigital = new EightDigital();
        System.out.println(eightDigital.bfs(start.toString()));
    }
}

class EightDigital {

    public int bfs(String start) {
        String end = "12345678x";
        Queue<String> q = new Queue<>();  // 存储当前位置信息
        HashMap<String, Integer> d = new HashMap<>(); // 存储每个位置信息对应移动的步数

        // 将起点位置放入队列中 Put the starting location into the queue
        q.push(start);
        // 将起点位置信息放入map中 Put the starting location info into the map
        d.put(start, 0);

        // 向四个方向移动的坐标 moving in four directions
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        while (!q.isEmpty()) {

            // 队头出队 The head of queue dequeue
            String t = q.front();
            q.pop();

            // 获取当前位置的距离 Gets the distance to the current position
            int distance = d.get(t);

            // 如果到达终点，返回距离 If the destination is reached, return the distance
            if (t.equals(end)) return distance;

            // 状态转移，将字符串转为数组下标
            int k = t.indexOf('x');  // x的坐标
            int x = k / 3;  // x的横坐标
            int y = k % 3;  // x的纵坐标

            // 判断四个方向是否都可以走，可以走的方向加入p中
            for (int i = 0; i < 4; i++) {

                int x1 = x + dx[i];
                int y1 = y + dy[i];

                // 如果可以走，将该点加入队列，距离+1 If you can go this point, add the point to the queue, distance +1
                if (x1 >= 0 && x1 < 3 && y1 >= 0 && y1 < 3) {

                    // 交换下标位置 Swap subscripts
                    t = SwapUtils.swap(k, x1 * 3 + y1, t);

                    // 记录当前位置 Record the current position
                    // 如果d中不存在该情况，将该情况加入d中，距离为当前情况的距离+1
                    if (!d.containsKey(t)) {
                        d.put(t, distance + 1);
                        q.push(t);
                    }

                    // 还原下标位置 Swap subscripts
                    t = SwapUtils.swap(k, x1 * 3 + y1, t);
                }
            }
        }
        return -1;
    }
}